class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> mem(n, vector<int>(n, -1));

        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i + 1 == j) return 0;

            if (mem[i][j] != -1) return mem[i][j];
            mem[i][j] = INT_MAX;
            for (int k = i + 1; k < j; ++k)
                mem[i][j] = min(mem[i][j], dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]);

            return mem[i][j];
            };

        return dfs(0, n - 1);
    }
};